package a10_动态规划;

/**
 * <p>
 * a08_整数拆分复习4
 * </p>
 *
 * @author flyduck
 * @since 2025/4/8
 */
public class a08_整数拆分复习4 {
    //dp[i]：整数i拆分后最大乘积

    //递推公式：
    //dp[j] * (i-j)
    //j * (i-j)

    //初始化：
    //dp[0]=0;
    //dp[1]=0;
    //dp[2]=1;
    public int integerBreak(int n) {
        int[] dp = new int[n+1];
        dp[0]=0;
        dp[1]=0;
        dp[2]=1;

        for (int i = 3; i <= n; i++) {
            for (int j = 1; j < i; j++) {
                dp[i] = Math.max(dp[i],Math.max(j * (i-j), dp[j] * (i-j)));
            }
        }

        return dp[n];

    }
}
